572. The lesson of mathematics

 

At the beginning of each lesson, the math teacher Guzel Zakievna writes a positive integer n on the board. During the lesson, the students try to find as many prime factors of this number as possible. At the end of the lesson, the generous Guzel Zakievna rewards all students who found the maximum number of prime factors with a candy.

Vasya, a student who loves sweets, asks for your help to secure a candy from Guzel Zakievna. For the given number n, print all its prime factors and the powers with which they occur in the number.

 

Input. One positive integer n (n ≤ 109).

 

Output. Print all the prime factors of the number n in ascending order. For each factor, specify the power with which it occurs in n, if the power is greater than one. The output format should match the example.

 

Sample input

Sample output

3240

2^3*3^4*5

 

 

SOLUTION

factorization

 

Algorithm analysis

The task is to factorize the number n. To do this, iterate through all its possible prime divisors from 2 to ​. For each divisor, count how many times it divides n.

 

Algorithm implementation

The factor function performs the factorization of n into its prime factors.

 

void factor(int n)

{

  for(int i = 2; i <= sqrt(n); i++)

  {

    if (n % i) continue;

 

The number i is a divisor of n. In the variable c, compute the power with which it appears in the factorization of n.

 

    int c = 0;

    while(n % i == 0) n /= i, c++;

 

Print the factor ic. If the power c = 1, print only i. Otherwise, print the factor i along with its power.

 

    if (c > 1) printf("%d^%d",i,c); else printf("%d",i);

 

If the number n is not fully factorized yet (n > 1), print a multiplication sign.

 

    if (n > 1) printf("*");

  }

 

If, after completing the loop, the value of n is greater than 1, it is a prime number.

 

  if (n > 1) printf("%d",n);

  printf("\n");

}

 

The main part of the program. Read the input number n and start its factorization.

 

scanf("%d",&n);

factor(n);

 

Python implementation

 

import math

 

The factor function performs the factorization of n into its prime factors.

 

def factor(n):

  for i in range(2, math.isqrt(n) + 1):

    if n % i: continue

 

The number i is a divisor of n. In the variable c, compute the power with which it appears in the factorization of n.

 

    c = 0

    while n % i == 0:

      n //= i

      c += 1

 

Print the factor ic. If the power c = 1, print only i. Otherwise, print the factor i along with its power.

 

    if c > 1: print(i,"^",c, sep = "", end="")

    else: print(i, end="")

 

If the number n is not fully factorized yet (n > 1), print a multiplication sign.

 

    if n > 1: print("*", end="")

 

If, after completing the loop, the value of n is greater than 1, it is a prime number.

 

  if n > 1: print(n)

  else: print()

 

The main part of the program. Read the input number n and start its factorization.

 

n = int(input())

factor(n)